Section: New Results

Exact asymptotics of random walks in the quarter plane

Participant : Guy Fayolle.

In collaboration with K. Raschel (CNRS, Université F. Rabelais à Tours), we pursued the works initiated in 2011.

The enumeration of planar lattice walks, is a classical topic in combinatorics. For a given set $𝒮$ of allowed unit jumps (or steps), it is a matter of counting the number of paths starting from some point and ending at some arbitrary point in a given time, and possibly restricted to some regions of the plane.

Like in the probabilistic context, a common way of attacking these problems relies on the following analytic approach. Let $f(i,j,k)$ denote the number of paths in ${\mathbb{Z}}_{+}^2$ starting from $(0,0)$ and ending at $(i,j)$ at time $k$. Then the corresponding CGF

satisfies the functional equation

where $x,y,z$ are complex variables, although the time variable $z$ plays somehow the role of a parameter. The question of the type of the associated counting generating functions, that is rational, algebraic, holonomic (solution of a linear differential equation with polynomial coefficients), was solved whenever the group is finite (see RA 2010). When the group is infinite, the problem is still largely.

It turns out that the nature of singularities play a deep important role in this classification. Making use of the general and powerful approach proposed in the book [2] , the paper [9] has been presented at the 23rd International Conference AofA 2012 on Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Montreal, June 17-22.